package cn.yuemouren.suanfa;

/**
 * @Author: Timi
 * @Description: 二分法拓展
 * @date 2021/3/31 下午3:35
 **/
public class BinarySearchExpand {

    public static void main(String[] args) {
        int[] arr = {1,2,3,5,7,8,8,8,9};
        System.out.println(findFirstValue1(arr,8));
        System.out.println(findFirstValue2(arr,8));
        System.out.println(findLastValue1(arr,8));
        System.out.println(findLastValue2(arr,8));
        System.out.println(findFirstDaValue1(arr,6));
        System.out.println(findFirstDaValue2(arr,6));
        System.out.println(findLastXiaoValue1(arr,6));
        System.out.println(findLastXiaoValue2(arr,6));
    }

    /**
     *  查找第一个值等于给定值的元素
     */
    public static int findFirstValue1(int[] arr,int value){
        int low = 0, high = arr.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] < value){
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        //终止条件
        if(low < arr.length && arr[low] == value){
            return low;
        }
        return -1;
    }

    public static int findFirstValue2(int[] arr,int value){
        int low = 0, high = arr.length - 1;

        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] < value){
                low = mid + 1;
            } else if(arr[mid] > value){
                high = mid - 1;
            } else {
                if(mid == 0 || arr[mid - 1] != value){
                    return mid;
                }
                high = mid - 1;
            }
        }
        return -1;
    }

    //查找最后一个值等于给定值的元素
    public static int findLastValue1(int[] arr,int value){
        int low = 0, high = arr.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] > value){
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        //终止条件
        if(high > 0 && arr[high] == value){
            return high;
        }
        return -1;
    }

    public static int findLastValue2(int[] arr,int value){
        int low = 0, high = arr.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] > value){
                high = mid - 1;
            } else if(arr[mid] < value){
                low = mid + 1;
            } else {
                if(mid == 0 || arr[mid + 1] != value){
                    return mid;
                }
                low = mid + 1;
            }
        }
        return -1;
    }

    //查找第一个大于等于给定值的元素
    public static int findFirstDaValue1(int[] arr,int value){
        int low = 0, high = arr.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] < value){
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        //终止条件
        if(low < arr.length && arr[low] >= value){
            return low;
        }
        return -1;
    }

    public static int findFirstDaValue2(int[] arr,int value){
        int low = 0, high = arr.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] >= value){
                if((mid == 0) || arr[mid - 1] < value){
                    return mid;
                }
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    //查找最后一个小于等于给定值的元素
    public static int findLastXiaoValue1(int[] arr,int value){
        int low = 0, high = arr.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] > value){
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        //终止条件
        if(high > 0 && arr[high] <= value){
            return high;
        }
        return -1;
    }

    public static int findLastXiaoValue2(int[] arr,int value){
        int low = 0, high = arr.length - 1;

        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if(arr[mid] <= value){
                if(mid == arr.length - 1 || arr[mid + 1] > value){
                    return mid;
                }
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
